package com.nowcoder.code.lcof;

public class JZ13 {

    public static void main(String[] args) {
        System.out.println(new JZ13().movingCount(10, 1, 100));
    }


    boolean[][] bs;

    public int movingCount(int threshold, int rows, int cols) {
        bs = new boolean[cols][rows];
        return recursion(threshold, rows, cols, 0, 0);
    }


    public int recursion(int threshold, int rows, int cols, int nr, int nc) {

        if (nr >= rows || nc >= cols || nr < 0 || nc < 0 || bs[nc][nr]) {
            return 0;
        }

        int sum = 0;
        if (nr == 100) {
            sum = 1;
        } else {
            sum = nr % 10 + nr / 10;
        }

        if (nc == 100) {
            sum++;
        } else {
            sum = nc % 10 + nc / 10 + sum;
        }

        if (threshold < sum) {
            return 0;
        }
        bs[nc][nr] = true;

        return 1 + recursion(threshold, rows, cols, nr + 1, nc) +
                recursion(threshold, rows, cols, nr - 1, nc) +
                recursion(threshold, rows, cols, nr, nc + 1) +
                recursion(threshold, rows, cols, nr, nc - 1);


    }

}
